package com.mlh.queque;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

/**
 * @author 缪林辉
 * @date 2024/3/23 19:21
 * @DESCRIPTION
 */
// 给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
// 返回 滑动窗口中的最大值 。
// 输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
// 输出：[3,3,5,5,6,7]
// 解释：
// 滑动窗口的位置                最大值
// ---------------               -----
// [1  3  -1] -3  5  3  6  7       3
// 1 [3  -1  -3] 5  3  6  7       3
// 1  3 [-1  -3  5] 3  6  7       5
// 1  3  -1 [-3  5  3] 6  7       5
// 1  3  -1  -3 [5  3  6] 7       6
// 1  3  -1  -3  5 [3  6  7]      7
public class MaxSlidingWindow {

    public static void main(String[] args) {
        int[] a= {1,3,-1,-3,5,3,6,7};
        int[] ints = MaxSlidingWindow.method1(a, 3);
        System.out.println(Arrays.toString(ints));

    }
    //初始思路 ：窗口每次最左的出去，最右的进来，实际上更新了一个数字而已
    // 判断出去的是不是最大值
    // 如果不是，直接让新进来的数和原本最小值进行比较
    // 如果是，可以在一开始保留最大值和次大值，这样新进来的数就和次大值进行比较即可
    // 该思路不可行，因为次大值没办法维护，例如 最大值 出去了  次大值顶上去  那谁顶次大值呢？

    /**
     * 首先要明确的是，题解中单调队列里的pop和push接口，仅适用于本题。
     * 单调队列不是一成不变的，而是不同场景不同写法，总之要保证队列里单调递减或递增的原则，所以叫做单调队列。
     * 不要以为本地中的单调队列实现就是固定的写法。
     */
    //代码随想录方法---> 单调队列  出口和入口要区分开
    // 设计单调队列的时候，pop，和push操作要保持如下规则：
    // pop(value)：如果窗口移除的元素value等于单调队列的出口元素，那么队列弹出元素，否则不用任何操作
    // push(value)：如果push的元素value大于入口元素的数值，那么就将队列入口的元素弹出，直到push元素的数值小于等于队列入口元素的数值为止
    // 保持如上规则，每次窗口移动的时候，只要访问队列出口的值就可以返回当前窗口的最大值。
    //这个方法实质上就维护好了次大值
    //去思考的他的规则你就能发现他维护好了最大值和次大值
    //因此这题就记住他的规则即可  没必要再去理解一遍  按单调队列的规则来做就可以得到答案
    public static int[] method1(int[] nums, int k) {
        if(k==1){return nums;}
        MonotonicQueue monotonicQueue = new MonotonicQueue();
        int len=nums.length-k+1;
        int[] res=new int[len];
        for (int i = 0; i < k; i++) {
            monotonicQueue.push(nums[i]);
        }
        res[0]=monotonicQueue.getFront();
        for (int i = k; i <nums.length; i++) {
            monotonicQueue.pop(nums[i-k]);
            monotonicQueue.push(nums[i]);
            res[i-k+1]=monotonicQueue.getFront();
        }
        return res;
    }

    public static int[] practice(int[] nums, int k) {
        int len=nums.length;
        int[]res=new int[len-k+1];
        MonotonicQueuePractice queue = new MonotonicQueuePractice();
        //将数组前K个数放入队列中
        for (int i = 0; i < k; i++) {
            queue.push(nums[i]);
        }
        //此时能够获取第一个窗口的最大值
        res[0]=queue.getHead();
        for (int i = 0; i < len-k; i++) {
            queue.pop(nums[i]);
            queue.push(nums[i+k]);
            res[i+1]=queue.getHead();
        }
        return res;
    }
}

class MonotonicQueue{
    Deque<Integer>deque=new LinkedList<>();
    public void pop(int val){
        if(!deque.isEmpty()&&val==deque.peek()){
            deque.pop();
        }
    }

    public void push(int val){
        while(!deque.isEmpty()&&deque.getLast()<val){
            deque.removeLast();
        }
        deque.addLast(val);
    }

    public int getFront(){
        return deque.peek();
    }
}

class MonotonicQueuePractice{
    Deque<Integer>queue=new LinkedList<>();
    public void pop(int val){
        if(!queue.isEmpty()&&val==queue.peek()){
            queue.pop();
        }
    }
    public void push(int val){
        while(!queue.isEmpty()&&queue.getLast()<val){//queue.getLast()<=val 这里不能取等于 如果数组是[7,7,7,7]你就会发现问题
            queue.removeLast();
        }
        queue.add(val);
    }
    public int getHead(){
        return queue.peek();
    }
}